package com.sheng.leetcode.year2025.month10.day17;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author by ls
 * @date 2025/10/17
 * <p>
 * 3003. 执行操作后的最大分割数量<p>
 * <p>
 * 给你一个下标从 0 开始的字符串 s 和一个整数 k。<p>
 * 你需要执行以下分割操作，直到字符串 s 变为 空：<p>
 * 选择 s 的最长 前缀，该前缀最多包含 k 个 不同 字符。<p>
 * 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。<p>
 * 执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。<p>
 * 在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的 最大 分割数量。<p>
 * <p>
 * 示例 1：<p>
 * 输入：s = "accca", k = 2<p>
 * 输出：3<p>
 * 解释：<p>
 * 最好的方式是把 s[2] 变为除了 a 和 c 之外的东西，比如 b。然后它变成了 "acbca"。<p>
 * 然后我们执行以下操作：<p>
 * 最多包含 2 个不同字符的最长前缀是 "ac"，我们删除它然后 s 变为 "bca"。<p>
 * 现在最多包含 2 个不同字符的最长前缀是 "bc"，所以我们删除它然后 s 变为 "a"。<p>
 * 最后，我们删除 "a" 并且 s 变成空串，所以该过程结束。<p>
 * 进行操作时，字符串被分成 3 个部分，所以答案是 3。<p>
 * <p>
 * 示例 2：<p>
 * 输入：s = "aabaab", k = 3<p>
 * 输出：1<p>
 * 解释：<p>
 * 一开始 s 包含 2 个不同的字符，所以无论我们改变哪个， 它最多包含 3 个不同字符，因此最多包含 3 个不同字符的最长前缀始终是所有字符，因此答案是 1。<p>
 * <p>
 * 示例 3：<p>
 * 输入：s = "xxyz", k = 1<p>
 * 输出：4<p>
 * 解释：<p>
 * 最好的方式是将 s[0] 或 s[1] 变为 s 中字符以外的东西，例如将 s[0] 变为 w。<p>
 * 然后 s 变为 "wxyz"，包含 4 个不同的字符，所以当 k 为 1，它将分为 4 个部分。<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length <= 10^4<p>
 * s 只包含小写英文字母。<p>
 * 1 <= k <= 26<p>
 */
public class LeetCode3003 {

    @Test
    public void test() {
//        String s = "accca";
//        int k = 2;
//        String s = "aabaab";
//        int k = 3;
        String s = "xxyz";
        int k = 1;
        System.out.println(new Solution().maxPartitionsAfterOperations(s, k));
    }
}

class Solution {
    public int maxPartitionsAfterOperations(String s, int k) {
        // 选择 s 的最长 前缀，该前缀最多包含 k 个 不同 字符。
        // 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。
        // 执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。
        // 在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的 最大 分割数量。
        // 需要记录字符串 s 中不同字符的数量，如果不同字符的数量大于 k，则需要进行操作
        // 如果不同字符的数量小于 k，则不需要进行操作，直接返回 1
        Map<Long, Integer> memo = new HashMap<>();
        return dfs(0, 0, 0, memo, s.toCharArray(), k);
    }

    private int dfs(int i, int mask, int changed, Map<Long, Integer> memo, char[] s, int k) {
        if (i == s.length) {
            return 1;
        }

        // 把参数压缩到一个 long 中，方便作为哈希表的 key
        long args = (long) i << 32 | mask << 1 | changed;
        // 之前计算过
        if (memo.containsKey(args)) {
            return memo.get(args);
        }

        int res;
        // 不改 s[i]
        int bit = 1 << (s[i] - 'a');
        int newMask = mask | bit;
        if (Integer.bitCount(newMask) > k) {
            // 分割出一个子串，这个子串的最后一个字母在 i-1
            // s[i] 作为下一段的第一个字母，也就是 bit 作为下一段的 mask 的初始值
            res = dfs(i + 1, bit, changed, memo, s, k) + 1;
            // 不分割
        } else {
            res = dfs(i + 1, newMask, changed, memo, s, k);
        }

        if (changed == 0) {
            // 枚举把 s[i] 改成 a,b,c,...,z
            for (int j = 0; j < 26; j++) {
                newMask = mask | (1 << j);
                if (Integer.bitCount(newMask) > k) {
                    // 分割出一个子串，这个子串的最后一个字母在 i-1
                    // j 作为下一段的第一个字母，也就是 1<<j 作为下一段的 mask 的初始值
                    res = Math.max(res, dfs(i + 1, 1 << j, 1, memo, s, k) + 1);
                    // 不分割
                } else {
                    res = Math.max(res, dfs(i + 1, newMask, 1, memo, s, k));
                }
            }
        }

        // 记忆化
        memo.put(args, res);
        return res;
    }
}
